/*
Date:20210425 13:42PM
key:充分利用昨天是否是二叉搜素树的递归保留法，先递归再靠返回值改变上一个。
    注意ListNode* &new_head，必须带着一个新指针在原链表末尾的时候保留新头，否则递归结束头都没有了。
 */
class Solution {
public:
    ListNode* rever(ListNode* head,ListNode* &new_head) 
    {
        if(head->next!=NULL)
        {
            ListNode*p= rever(head->next,new_head);
            
            p->next=head;
            //cout<<head->val;
            head->next=NULL;
            //cout<<new_head->val;
            return head;
        }
        else
        {
            new_head=head;
            //cout<<new_head->val;
            return head;
        }
    }
    ListNode* reverseList(ListNode* head) 
    {
        if(head==NULL){return NULL;}
        ListNode*new_head=NULL;
        rever(head,new_head) ;
        
        return new_head;
    }
};